package leetcode.weekly.week297;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.H;

//Solution3Test
public class Solution5 implements IDebug {

	int len;

	public int distributeCookies(int[] cookies, int k) {
		this.len = cookies.length;
		Integer[][] dp = new Integer[k + 1][1 << len];
		// cookies零食包，分给k个孩子，分配状态(被占用)，还有几个零食包可以分。
		return this.distributeCookies(cookies, k, 0, this.len, dp);
	}

	// rest可以通过数used与limit的差值（异或）中的1数出来，为了方便，rest单独记录，省着每个孩子都数一遍
	private int distributeCookies(int[] cookies, int k, int used, int rest, Integer[][] dp) {
		// 如果剩下一个孩子
		if (k == 1) {
			// 不用想，都给他
			int sum = 0;
			for (int i = 0; i < len; i++) {
				int cur = 1 << i;
				if ((used & cur) == 0) {
					sum += cookies[i];
				}
			}
			return sum;
		}
		// 还有k个孩子没有分，已经分过的零食包情况为used，无论前面孩子怎么分成的这种情况，只要满足k used条件，这种情况下答案就是定数
		if (dp[k][used] != null) {
			return dp[k][used];
		}
		// 在k，used状态下，期望的最优解是什么
		int ans = Integer.MAX_VALUE;
		// 有rest个包，就有status种组合的尝试
		int status = 1 << rest;
		// 每一种尝试
		for (int i = 1; i < status; i++) {
			int takeSize = 0;// 这个孩子拿了几包
			int takeNum = 0;// 这个孩子拿了多少块
			int myTakeStatus = 0;// 哪些原数组的零食包被这个孩子拿走了
			// 检查原零食包，f=0是剩下rest中的第一个可用包
			for (int j = 0, f = 0; j < len; j++) {
				int cur = 1 << j;
				// 原数组中这包还有
				if ((used & cur) == 0) {
					// 在status的i这次尝试中，这个零食包要分给当前这个孩子
					if ((i & (1 << f)) != 0) {
						takeSize++;// 分得数量增加1
						myTakeStatus |= cur;// 标记为占用
						takeNum += cookies[j];// 这个孩子累计拿了多少块饼干
					}
					f++;// 检查下一个可用
				}
			}
			// i作为status的一种情况，当前孩子拿了take个饼干与后续孩子分得的最小，两者较大的是这种尝试的结果
			int tryAns = Math.max(takeNum,
					this.distributeCookies(cookies, k - 1, used | myTakeStatus, rest - takeSize, dp));
			// 所有尝试中最小的，是当前孩子在零食包被占用情况为used下的期望结果
			ans = Math.min(ans, tryAns);
		}
		dp[k][used] = ans;
		return ans;
	}

	@Override
	public void debug4() {

		H.compare(31, this.distributeCookies(H.str2array3("[8,15,10,20,8]"), 2));
		H.compare(7, this.distributeCookies(H.str2array3("[6,1,3,2,2,4,1,2]"), 3));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution5 so = new Solution5();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
